package com.study.lihan.letcode.offer;

import com.sun.org.apache.xerces.internal.dom.PSVIAttrNSImpl;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: lihan
 * @Date : 2022/9/24- 09
 * @DESCRIPTION: com.study.lihan.letcode.offer
 * 输入一个数组，如何找出数组中所有和为0的3个数字的三元组？需要注意的是，返回值中不得包含重复的三元组。
 * 例如，在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，它们分别是[-1，0，1]和[-1，-1，2]。
 * @version: 1.0
 */
public class T7 {
    public static void main(String[] args) {

        int[] arrs = {-1,0,1,2,-1,-4};
        arrs = new int[0];
        System.out.println(threeSum(arrs));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        nums = stackSort(nums);
        int preVal = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int firstVal = nums[i];
            if (firstVal == preVal){
                continue;
            }
            int secIndex = i +1;
            int thirdIndex = nums.length -1;
            int secVal =Integer.MAX_VALUE;
            while (secIndex < thirdIndex ){
                if (nums[secIndex] + nums[thirdIndex] == -firstVal && nums[secIndex] != secVal){
                    secVal = nums[secIndex];
                    List<Integer> tempList= new ArrayList<>();
                    tempList.add(firstVal);
                    tempList.add(nums[secIndex]);
                    tempList.add(nums[thirdIndex]);
                    result.add(tempList);
                    secIndex++;
                    thirdIndex --;
                    preVal = firstVal;
                    continue;
                }
                if (nums[secIndex] + nums[thirdIndex] < -firstVal){
                    secIndex++;
                    continue;
                }
                thirdIndex--;
            }


        }
        return result;

    }

    //堆排序，不稳定
    public static int[] stackSort(int[] arr){
        int[] resultArr =  new int[arr.length];
        int len = arr.length - 1;
        int tail = (len -1)/2;
        for (int i = tail; i >=0 ; i--) {
            shift(arr, i, len);
        }
        int curIndex = len;
        while (curIndex != 0){
            resultArr[len - curIndex] = arr[0];
            arr[0] = arr[curIndex];
            curIndex --;
            shift(arr, 0, curIndex);
        }
        resultArr[len - curIndex] = arr[0];
        return resultArr;

    }
    public static void shift (int[] arr, int low, int high){
        int curIndex = low;
        int minValIndex = -1;
        while (curIndex <= high){
            minValIndex = 2 * curIndex +1;
            if (minValIndex > high){
                return;
            }
            if (minValIndex +1 <= high && arr[minValIndex + 1] < arr[minValIndex]){
                minValIndex++;
            }
            if ( arr[minValIndex] > arr[curIndex]){
                return;
            }
            int temp = arr[minValIndex];
            arr[minValIndex] = arr[curIndex];
            arr[curIndex]=  temp;
            curIndex = minValIndex;
        }
    }
}
